1. Technical Field
The present invention relates in general to an improved data processing system, and in particular to an improved method and system for compressing data. Still more particularly, the present invention relates to an improved method and system for compressing a block of data using a sorting network.
2. Description of the Related Art
Sliding window lossless data compression was originally described in 1977 in an article entitled "A Universal Algorithm for Sequential Data Compression," by Ziv and Lempel, in IEEE Transactions on Information Theory, 1977. The principle has been described succinctly as "dictionary based compression using previously seen text as the dictionary."
Data compression algorithms may conceptually be divided into two parts: a front-end, data modeling part; and a back-end, output coding part. A primary function of the front-end or data modeling phase of data compression systems--especially LZ based data compression systems--is to locate identical runs or strings of input bytes in the input data.
Efficient hardware for performing such a front-end task in a sliding window, data compression system has been invented by Craft, and is described in U.S. patent application Ser. No. 08/290,451 entitled "Method and Apparatus for Compressing Data." The Craft invention uses a content addressable memory (CAM) with a rotating selector bit register. In U.S. Pat. No. 5,003,307 to Whiting, et al. entitled "Data Compression Apparatus With Shift Register Search Means," a similar approach using a content addressable shift-register is disclosed. The Craft invention can process a byte per cycle, with few gate delays, which is as fast as the data can be delivered to the compression engine in a stream compression paradigm. However, data in computer systems is often available for compression as a block of data, as opposed to a stream of bytes. For example, in data processing systems, fixed-size disk blocks of 4,096 bytes are submitted to a compression engine for compression and decompression at the same time.
Sorting networks, such as those described in "Sorting Networks and Their Applications" by K. E. Batcher, in Proceedings AFIPS Spring Joint Conference, Volume 32, pages 307-314, are used in switching systems to route a large number of addressed packets, all of which arrive at the switch at the same time in parallel, to a number of output ports. For data compression implemented in software, sorting based approaches are inferior to hashing based approaches because they take O(n log.sup.2 (n)) steps.
Therefore, there remains a need for a method and system that can quickly and efficiently compress a block of data while maximizing the amount of data processing that may be performed in parallel.